package com.zyk.leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangsan
 * @date 2021/4/15 14:24
 */
public class C130 {

    // https://leetcode-cn.com/problems/surrounded-regions/
    // DFS, 从边上开始, 把中间的O改成X, 最后没有被改的就是被包围的
    public static void solve(char[][] board) {
        int R = board.length;
        int C = board[0].length;
        // 去玩第1列, 和最后1列
        for (int r = 0; r < R; r++) {
            dfs(board, r, 0, R, C);
            dfs(board, r, C - 1, R, C);
        }
        // 去玩第1行, 和最后一行
        for (int c = 1; c < C - 1; c++) {
            dfs(board, 0, c, R, C);
            dfs(board, R - 1, c, R, C);
        }
        // 最后修改的字符都是没有被包围的, 没有被修改的O都是被包围的
        for (char[] num : board) {
            for (int i = 0; i < num.length; i++) {
                if (num[i] == '\0') num[i] = 'O';
                else if (num[i] == 'O') num[i] = 'X';
            }
        }
    }

    private static void dfs(char[][] board, int r, int c, int R, int C) {
        if (r < 0 || r == R || c < 0 || c == C || board[r][c] != 'O') return;
        board[r][c] = '\0';
        dfs(board, r + 1, c, R, C);
        dfs(board, r - 1, c, R, C);
        dfs(board, r, c + 1, R, C);
        dfs(board, r, c - 1, R, C);
    }

    // BFS, 宽度优先遍历. 先把四个边的加入队列, 然后队列弹出一个坐标,添加他的上下左右
    public static void solve2(char[][] board) {
        int R = board.length;
        int C = board[0].length;
        Queue<int[]> queue = new LinkedList<>();
        // 去玩第1列, 和最后1列
        for (int r = 0; r < R; r++) {
            if (board[r][0] == 'O') queue.add(new int[]{r, 0});
            if (board[r][C - 1] == 'O') queue.add(new int[]{r, C - 1});
        }
        // 去玩第1行, 和最后一行
        for (int c = 1; c < C - 1; c++) {
            if (board[0][c] == 'O') queue.add(new int[]{0, c});
            if (board[R - 1][c] == 'O') queue.add(new int[]{R - 1, c});
        }
        // bfs
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        while (!queue.isEmpty()) {
            int[] coord = queue.poll();
            int r = coord[0], c = coord[1];
            board[r][c] = '\0';
            for (int i = 0; i < 4; i++) {
                int mx = r + dx[i], my = c + dy[i];
                if (mx < 0 || my < 0 || mx == R || my == C || board[mx][my] != 'O') {
                    continue;
                }
                queue.offer(new int[]{mx, my});
            }
        }
        // 最后修改的字符都是没有被包围的, 没有被修改的O都是被包围的
        for (char[] num : board) {
            for (int i = 0; i < num.length; i++) {
                if (num[i] == '\0') num[i] = 'O';
                else if (num[i] == 'O') num[i] = 'X';
            }
        }
    }

    // 并查集版本
    public static void solve3(char[][] board) {
        int R = board.length, C = board[0].length, size = R * C;
        UnionSet un = new UnionSet(size + 1);       // 多留一个位置, 和边相关的点和他连
        // 先把边的O的关联在一起, 然后在遍历,和上下左右的O关联, 最后如果和 预留的那个在一组的就是没有被包围的, 其他的就是被包围的了
        for (int r = 0; r < R; r++) {
            if (board[r][0] == 'O') un.union(index(r, 0, C), size);
            if (board[r][C - 1] == 'O') un.union(index(r, C - 1, C), size);
        }
        // 去玩第1行, 和最后一行
        for (int c = 1; c < C - 1; c++) {
            if (board[0][c] == 'O') un.union(index(0, c, C), size);
            if (board[R - 1][c] == 'O') un.union(index(R - 1, c, C), size);
        }

        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (board[r][c] == 'O') {
                    if (r - 1 >= 0 && board[r - 1][c] == 'O') {
                        un.union(index(r - 1, c, C), index(r, c, C));
                    }
                    if (r + 1 < R && board[r + 1][c] == 'O') {
                        un.union(index(r + 1, c, C), index(r, c, C));
                    }
                    if (c - 1 >= 0 && board[r][c - 1] == 'O') {
                        un.union(index(r, c - 1, C), index(r, c, C));
                    }
                    if (c + 1 < C && board[r][c + 1] == 'O') {
                        un.union(index(r, c + 1, C), index(r, c, C));
                    }
                }
            }
        }

        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if( board[r][c] == 'O' && !un.isSameSet( index(r, c, C), size ) ) {
                    board[r][c] = 'X';
                }
            }
        }
    }

    public static class UnionSet {
        int[] parent;
        private int[] size;
        private int[] help;
        private int sets;

        public UnionSet(int n) {
            parent = new int[n];
            size = new int[n];
            help = new int[n];
            sets = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        private int findHead(int i) {
            // 减少寻址的时间，即把i所在的并集中的元素的父亲都设置成为i的头，然后在寻找它们的时候就能很快地找到那个头
            int helpIndex = 0;
            while (i != parent[i]) {
                help[helpIndex++] = i;
                i = parent[i];
            }
            while (helpIndex > 0) {
                parent[help[--helpIndex]] = i;
            }
            return i;
        }

        /**
         * 是否同一组
         */
        public boolean isSameSet(int a, int b) {
            return findHead(a) == findHead(b);
        }

        public void union(int i, int j) {
            int headI = findHead(i);
            int headJ = findHead(j);
            if (headI != headJ) {
                if (size[headI] >= size[headJ]) {
                    parent[headJ] = headI;
                    size[headI] += size[headJ];
                    size[headJ] = 0;
                } else {
                    parent[headI] = headJ;
                    size[headJ] += size[headI];
                    size[headI] = 0;
                }
                sets--;
            }
        }

        public int sets() {
            return sets;
        }
    }

    // 二维数组的下标转换成一维数组的下标
    public static int index(int x, int y, int width) {
        return x * width + y;
    }


    // for test
    public static void main(String[] args) {
        char[][] board = {
                {'X', 'X', 'X', 'X'},
                {'X', 'O', 'O', 'X'},
                {'X', 'X', 'O', 'X'},
                {'X', 'O', 'X', 'X'}};
//        solve(board);
//        solve2(board);
        solve3(board);
        for (char[] arr : board) {
            System.out.println(Arrays.toString(arr));
        }
    }


}
